#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>

using namespace std;


struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution
{
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root)
    {
        string path;
        dfs(root, path);
        return ret;
    }
    void dfs(TreeNode* root, string path)
    {
        if (root == nullptr) return;
        if (root->left == nullptr && root->right == nullptr)
        {
            ret.push_back(path += to_string(root->val));
            return;
        }
        path += to_string(root->val);
        path += "->";
        if (root->left) dfs(root->left, path);
        if (root->right) dfs(root->right, path);
    }
};
 
//class Solution
//{
//    vector<string> ret;
//public:
//    vector<string> binaryTreePaths(TreeNode* root)
//    {
//        if (root->left == nullptr && root->right == nullptr)
//        {
//            ret.push_back(to_string(root->val));
//            return ret;
//        }
//        string path;
//        path += to_string(root->val);
//        path += "->";
//        dfs(root->left, path);
//        dfs(root->right, path);
//        return ret;
//    }
//    void dfs(TreeNode* root, string path)
//    {
//        if (root == nullptr) return;
//        if (root->left == nullptr && root->right == nullptr)
//            ret.push_back(path += to_string(root->val));
//        path += to_string(root->val);
//        path += "->";
//        if (root->left) dfs(root->left, path);
//        if (root->right) dfs(root->right, path);
//    }
//};